package Tree;

import java.util.*;

public class _684_RedundantConnection {
    Set<Integer> totalVals = new HashSet<>();
    List<Set<Integer>> seens = new ArrayList<>();
    public int[] findRedundantConnection_1(int[][] edges) {
        int[] res = new int[2];
        for (int[] edge:edges) {
            if (totalVals.contains(edge[0]) && totalVals.contains(edge[1])) {
                boolean circle = false;
                for (Set<Integer> seen : seens) {
                    if (seen.contains(edge[0]) && seen.contains(edge[1])) {
                        res[0] = edge[0];
                        res[1] = edge[1];
                        circle = true;
                    }
                }
                if (!circle) {
                    boolean firstOne = false;
                    Set<Integer> first = null;
                    Set<Integer> second = null;
                    int removePos = 0;
                    for (int i = 0; i < seens.size(); i++) {
                        Set<Integer> seen = seens.get(i);
                        if (seen.contains(edge[0]) || seen.contains(edge[1])) {
                            if (!firstOne) {
                                first = seen;
                                firstOne = true;
                            } else {
                                second = seen;
                                removePos = i;
                                break;
                            }
                        }
                    }
                    first.addAll(second);
                    seens.remove(removePos);
                }
            } else {
                boolean contain = false;
                for (int i = 0; i < seens.size(); i++) {
                    Set<Integer> seen = seens.get(i);
                    if (seen.contains(edge[0])) {
                        contain = true;
                        seen.add(edge[0]);
                        seens.remove(i);
                        seens.add(seen);
                        break;
                    } else if (seen.contains(edge[1])) {
                        contain = true;
                        seen.add(edge[1]);
                        seens.remove(i);
                        seens.add(seen);
                        break;
                    }
                }
                if (!contain) {
                    Set<Integer> set = new HashSet<>();
                    set.add(edge[0]);
                    set.add(edge[1]);
                    seens.add(set);
                }
                totalVals.add(edge[0]);
                totalVals.add(edge[1]);
            }
        }
        return res;
    }

    public int[] findRedundantConnection(int[][] edges) {
        Map<Integer, Integer> parent = new HashMap<>();
        for(int[] edge: edges){
            Integer e0 = p(parent, edge[0]);
            Integer e1 = p(parent, edge[1]);

            if(e0 == null && e1 == null){ //both are new, new graph
                parent.put(edge[0], edge[0]);
                parent.put(edge[1], edge[0]);
            }
            else if(e0 == e1){
                return edge;
            }
            else if(e0 != null && e1 != null && e0 != e1){ //different graphs, connect
                parent.put(e1, e0);
            }
            else{//connect the one node up
                if(e0 == null){
                    parent.put(edge[0], e1);
                }
                else{
                    parent.put(edge[1], e0);
                }
            }
        }
        return null;
    }

    public Integer p(Map<Integer, Integer> parent, int i){
        Integer p = parent.get(i);
        while(p != parent.get(p)) p = parent.get(p);
        return p;
    }
}
